﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/fair-candy-swap/
/*
题目描述：
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，
bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。
一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，
answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。
题目测试用例保证存在与输入对应的答案。

示例 1：
输入：aliceSizes = [1,1], bobSizes = [2,2]
输出：[1,2]

示例 2：
输入：aliceSizes = [1,2], bobSizes = [2,3]
输出：[1,2]

示例 3：
输入：aliceSizes = [2], bobSizes = [1,3]
输出：[2,3]

示例 4：
输入：aliceSizes = [1,2,5], bobSizes = [2,4]
输出：[5,4]
 

提示：
1 <= aliceSizes.length, bobSizes.length <= 104
1 <= aliceSizes[i], bobSizes[j] <= 105
爱丽丝和鲍勃的糖果总数量不同。
题目数据保证对于给定的输入至少存在一个有效答案。
*/

// 方法1——暴力法
/*
思路：
枚举出所有可能的交换集合，求出交换后的两个数组的总和是否相同，如果相同则返回。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* fairCandySwap1(int* aliceSizes, int aliceSizesSize, int* bobSizes, int bobSizesSize, int* returnSize) {
	assert(aliceSizes && bobSizes && returnSize);
	*returnSize = 2;
	int* answer = (int*)malloc(2 * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	int i = 0;
	int j = 0;
	for (i = 0; i < aliceSizesSize; i++) {
		for (j = 0; j < bobSizesSize; j++) {
			// 交换
			int temp = aliceSizes[i];
			aliceSizes[i] = bobSizes[j];
			bobSizes[j] = temp;
			// 求和
			int aliceSum = 0;
			int bobSum = 0;
			for (int p1 = 0; p1 < aliceSizesSize; p1++) {
				aliceSum += aliceSizes[p1];
			}
			for (int p2 = 0; p2 < bobSizesSize; p2++) {
				bobSum += bobSizes[p2];
			}
			if (aliceSum == bobSum) {
				answer[1] = aliceSizes[i];
				answer[0] = bobSizes[j];
				return answer;
			}
			// 最后还要再交换回来
			bobSizes[j] = aliceSizes[i];
			aliceSizes[i] = temp;
		}
	}
	return answer;
}
// 时间复杂度：O(mn(m+n))，其中m和n分别为alice和bob数组的长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——数学法
/*
思路：
该方法类似于二分法中mid的求法：mid = left + (right - left) / 2
我们可以先求出alice数组的总和aliceSum和bob数组的总和bobSum，求出他们的差d = aliceSum - BobSum
然后遍历两个数组，如果发现aliceSizes[i] - bobSizes[j] = d / 2, 那么就直接将这两个元素写入answer数组。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* fairCandySwap2(int* aliceSizes, int aliceSizesSize, int* bobSizes, int bobSizesSize, int* returnSize) {
	assert(aliceSizes && bobSizes && returnSize);
	*returnSize = 2;
	int* answer = (int*)malloc(2 * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	int i = 0;
	int j = 0;
	int aliceSum = 0;
	int bobSum = 0;
	for (i = 0; i < aliceSizesSize; i++) {
		aliceSum += aliceSizes[i];
	}
	for (i = 0; i < bobSizesSize; i++) {
		bobSum += bobSizes[i];
	}
	int d = aliceSum - bobSum;
	for (i = 0; i < aliceSizesSize; i++) {
		for (j = 0; j < bobSizesSize; j++) {
			if (aliceSizes[i] - bobSizes[j] == d / 2) {
				answer[0] = aliceSizes[i];
				answer[1] = bobSizes[j];
				return answer;
			}
		}
	}
	return answer;
}
// 时间复杂度：O(mn)，其中m和n分别为alice和bob的数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。
